/*

基本思路：
我们可以通过构建一个二维 DP 数组 dp[i][j]，其中 i 表示 T 中的前 i 个字符，j 表示 S 中的前 j 个字符。dp[i][j] 表示 S[0...j-1] 是否是 T[0...i-1] 的子序列。

转移方程：
如果 T[i-1] == S[j-1]，则 dp[i][j] = dp[i-1][j-1]。
如果 T[i-1] != S[j-1]，则 dp[i][j] = dp[i-1][j]。
边界条件：
dp[0][j] = 0（T 为空，S不是任何 T 的子序列）。
dp[i][0] = 1（S 为空时，任何 T 都包含空子序列）。
复杂度：
时间复杂度：O(m * n)，其中 m 是 T 的长度，n 是 S 的长度。
空间复杂度：O(m * n)。
*/


/*
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

    dp 是一个二维布尔数组，表示为 m+1 行、n+1 列。
    它由 vector<bool> 组成的数组（即每行是一个布尔向量）。

初始化：
    外层 vector 的大小为 m+1，即有 m+1 行。
    内层 vector<bool> 的大小为 n+1，即每行有 n+1 列。
    默认值是 false，因此 dp 的每个元素在初始化时为 false。
*/

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool isSubsequence(const string& T, const string& S) {
    int m = T.size();
    int n = S.size();
    
    // DP table, dp[i][j] means whether S[0..j-1] is a subsequence of T[0..i-1]
    vector<vector<bool> > dp(m + 1, vector<bool>(n + 1, false));

    // Empty S is always a subsequence of any prefix of T
    for (int i = 0; i <= m; i++) {
        dp[i][0] = true;  // An empty string is a subsequence of any string
    }

    // Fill the DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (T[i - 1] == S[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];  // Characters match, extend subsequence
            } else {
                dp[i][j] = dp[i - 1][j];  // Otherwise, skip current character in T
            }
        }
    }

    return dp[m][n];  // The answer is whether full S is subsequence of full T
}

int main() {
    string T = "abcde";
    string S = "ace";

    if (isSubsequence(T, S)) {
        cout << S << " is a subsequence of " << T << endl;
    } else {
        cout << S << " is NOT a subsequence of " << T << endl;
    }

    return 0;
}

/*
解释：
初始化：我们初始化了一个二维 dp 数组，dp[i][j] 表示 S[0...j-1] 是否是 T[0...i-1] 的子序列。
边界条件：dp[i][0] = true，表示任何字符串 T[0...i-1] 都包含空字符串 S。而 dp[0][j] 总是 false，因为空字符串 T 不能包含任何非空的 S。
递推关系：我们遍历每个字符，检查 T[i-1] 和 S[j-1] 是否相同。如果相同，则继承前一个状态 dp[i-1][j-1]；如果不同，则继承前一个字符的状态 dp[i-1][j]。
最终结果：最后返回 dp[m][n]，即 S 是否是 T 的子序列。
*/
